package com.lihepeng.leecode.sort;

/**
 * 最大堆
 * 1、如果某个节点 A 比它的子节点（中的一个）小，那么 A 就不配做父节点，应该下去，下面那个更大的节点上来做父节点，这就是对 A 进行下沉。
 * 2、如果某个节点 A 比它的父节点大，那么 A 不应该做子节点，应该把父节点换下来，自己去做父节点，这就是对 A 的上浮。
 */
public class MaxQ<Key extends Comparable<Key>> {
    // 集合
    private Key[]pq;
    // 数组中的元素数量
    private int size;

    public MaxQ(int size) {
        this.size = size;
        // 索引 0 不使用 所以多分配一个
        this.pq = (Key[]) new Comparable[size+1];
    }
    public Key max(){
        return pq[1];
    }
    public void insert(Key key) {

    }
    public void delMax(){

    }
    // 上浮
    private void swim(){

    }
    // 下沉
    private void sink() {

    }
    // 交换
    private void sweap(int i,int j) {
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }
    private int left(int root) {
        return root*2;
    }
    private int right(int root) {
        return root/2+1;
    }
    private int parent(int node) {
        return node/2;
    }


    /**
     *
     * pq[i]是不是小于pq[j]
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i,int j) {
        return pq[i].compareTo(pq[j])<0;
    }

}
